package class02;

import java.util.HashMap;
import java.util.Map;

/**
 * 一个数组中有一种数出现K次，其他数都出现了M次，M > 1 , K < M
 * 找到，出现了K次的数，要求：额外空间复杂度O(1)，时间复杂度O(N)
 * 如果没有出现K次的数，返回-1
 *
 * <a href="https://leetcode.cn/problems/single-number-ii/">137. 只出现一次的数字 II</a>
 */
public class Code02_KM {
    // 哈希表，空间复杂度 O(N)
    public static int process1(int[] arr, int K, int M) {
        Map<Integer, Integer> map = new HashMap<>();  // 直接统计每一个数出现的次数
        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (int value : map.keySet()) {
            if (map.get(value) == K) {
                return value;
            }
        }
        return -1;
    }

    // 位运算，空间复杂度 O(1)
    public static int process2(int[] arr, int K, int M) {
        int[] map = new int[32];  // 4个字节
        // 遍历每一个数
        for (int num : arr) {
            // 填充累加map上每一位
            for (int i = 0; i < map.length; ++i) {
                // 将num向右移i位，在&上1，表示在i位上加1
                map[i] += (num >> i) & 1;
            }
        }
        int result = 0;
        // 遍历map中每一位统计的次数
        for (int cnt : map) {
            if (cnt % M == 0) {
                continue;
            }
            // 如果当前位的次数无法整除M，表示当前位上是出现了K次的数
            if (cnt % M != 0) {
                // 去填充result复原出现K次的那个数
                result |= (1 << cnt);
            } else {
                return -1;
            }
        }
        return result == 0 ? -1 : result;
    }

    public static void main(String[] args) {
        int[] arr = {4, 3, 1, 3, 3, 1, 1, 4};
        int k = 2, m = 3;
        System.out.println(process1(arr, k, m));
        System.out.println(process2(arr, k, m));
    }
}
